package sort;


public class MergeSort {
	
	
	public static int[] tmp;

	public static void mergeSort1(int[] array,int l,int r) {
		//如过区间只要1个元素或者下标越界，直接返回
		if(l>=r) {
			return ;
		}
		//划分区间=》找中间点
		int mid=l+(r-l)/2;
		
		//划分左区间
		mergeSort1(array, l, mid);
		//左区间无法划分时，划分右区间
		mergeSort1(array, mid+1, r);

		//合并区间： [l,mid]+[mid+1,r] => [l,r]
		//tmp=new int[r-l+1]  =>可以在递归中定义，但每次递归均需要定义，因此建议写成全局变量
		int p1=l,p2=mid+1,p=0;
		while(p1<=mid&&p2<=r) {
			tmp[p++]=(array[p1]<array[p2])?array[p1++]:array[p2++];
		}
		while(p2<=r) {
			tmp[p++]=array[p2++];
		}
		while(p1<=mid) {
			tmp[p++]=array[p1++];
		}
		
		//将合并后的数组还原到原数组
		for(int i=l;i<=r;i++) {
			array[i]=tmp[i-l];
		}
	}
	
	//归并排序--非递归
	public static void merge(int[] array,int l,int mid,int r) {
		int s1=l,end1=mid;
		int s2=mid+1,end2=r;
		int i=0;
		int[] tmp=new int[r-l+1];
		while(s1<=end1&&s2<=end2) {
			if(array[s1]<=array[s2]) {
				tmp[i++]=array[s1++];
			}
			else if(array[s1]>array[s2]) {
				tmp[i++]=array[s2++];
			}
		}
		while(s1<=end1) {
			tmp[i++]=array[s1++];
		}
		while(s2<=end2) {
			tmp[i++]=array[s2++];
		}
		for(int x:tmp) {
			array[l++]=x;
		}
	}
	public static void mergeSort2(int[] array) {
		//gap: 当前进行合并的数组的元素个数
		int gap=1;
		//当gap>=arr.length，说明整个数组已经进行了合并
		while(gap<array.length) {
			//遍历每个子数组的起点位置
			for(int i=0;i<array.length;i=i+2*gap) {
				//需要合并子数组1和子数组2
				//因此，合并完成后i的值为i+2*gap,因为其合并的是两个gap大小的数组
				
				//子数组1的起点为left-> i
				//子数组1的终点为mid -> i+gap-1
				//子数组2的终点为right -> mid+gap
				int left=i;
				int mid=left+gap-1;
				if(mid>=array.length) {  //如果越界，就改为数组长度
					mid=array.length-1;
				}
				int right=gap+mid;
				if(right>=array.length) {//如果越界，就改为数组长度
					right=array.length-1;
				}
				merge(array, left, mid, right); //确定合并数组的边界后，合并两个数组
			}
			gap*=2; //现在数组大小变为2*gap，因此gap*=2
		}
		
	}
	public static void sortArray(int[] nums) {
		//tmp=new int[nums.length];
		//mergeSort1(nums, 0, nums.length-1);
		mergeSort2(nums);
	}
	public static void main(String[] args) {
		int[] arr=new int[] {9,6,3,7,8,2,0,1,4,10,2,3,5};
		sortArray(arr);
		for(int x:arr) {
			System.out.print(x+" ");
		}
	}

}
